package leetcode.tree;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/**
 * @author wangmaolin1
 * @date 2021/12/26 下午9:45
 */
public class _112路径总和2 {
    static List<List<Integer>> result= new LinkedList<>();
    static Stack<Integer> path=new Stack<>();
    /*
      给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
     */
    public static List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return result;
        }
        dfs(root, targetSum);
        return result;
    }

    private static void dfs(TreeNode root, int targetSum) {
        if (root == null) {
            return;
        }
        path.push(root.val);
        if (root.left == null && root.right == null) {
            if (root.val == targetSum) {
                result.add(new LinkedList<>(path));
            }
        }
        dfs(root.left, targetSum - root.val);
        dfs(root.right, targetSum - root.val);
        //当前节点左右子树都遍历完了，需要将当前节点从 path移除掉
        path.pop();

    }

    /*
            5
          4     8
       11     13  4
     7   2       6  1
     */
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left=new TreeNode(4);
        root.right=new TreeNode(8);
        root.left.left=new TreeNode(11);
        root.right.left=new TreeNode(13);
        root.right.right=new TreeNode(4);
        root.left.left.left=new TreeNode(7);
        root.left.left.right=new TreeNode(2);
        root.right.right.left=new TreeNode(5);
        root.right.right.right=new TreeNode(1);
        System.out.println(pathSum(root,22));
    }

    public boolean hasPathSum2(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.val == targetSum && node.left == null && node.right == null) {
                return true;
            }
            if (node.left != null) {
                node.left.val += node.val;
                queue.offer(node.left);
            }
            if (node.right != null) {
                node.right.val += node.val;
                queue.offer(node.right);

            }
        }
        return false;
    }

    public static class QueueData {
        TreeNode node;
        int sum;

        public QueueData(TreeNode node, int sum) {
            this.node = node;
            this.sum = sum;
        }
    }

}
